Search results for "Universal cycle"

showing 1 items of 1 documents

Universal Lyndon Words

2014

A word w over an alphabet Σ is a Lyndon word if there exists an order defined on Σ for which w is lexicographically smaller than all of its conjugates (other than itself). We introduce and study universal Lyndon words, which are words over an n-letter alphabet that have length n! and such that all the conjugates are Lyndon words. We show that universal Lyndon words exist for every n and exhibit combinatorial and structural properties of these words. We then define particular prefix codes, which we call Hamiltonian lex-codes, and show that every Hamiltonian lex-code is in bijection with the set of the shortest unrepeated prefixes of the conjugates of a universal Lyndon word. This allows us t…

Discrete mathematicsExistential quantificationLyndon word Universal cycle Universal Lyndon wordComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Lyndon word Universal cycle Universal Lyndon word Lex-codeLexicographical orderLyndon wordUniversal Lyndon wordLyndon wordsPrefixCombinatoricsMathematics::Group TheoryCombinatorics on wordsComputer Science::Discrete MathematicsUniversal cycleBijectionAlphabetMathematics::Representation TheoryComputer Science::Formal Languages and Automata TheoryMathematics
researchProduct